/*
https://leetcode-cn.com/problems/combination-sum-ii/solution/zu-he-zong-he-ii-by-leetcode-solution/
 */
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int candidate : candidates) {
            map.put(candidate,map.getOrDefault(candidate,0)+1);
        }
        List<Map.Entry<Integer,Integer>> list=new ArrayList<>(map.entrySet());
        list.sort((a,b)->b.getKey()-a.getKey());
        List<List<Integer>> ans=new ArrayList<>();
        List<Integer> temp=new ArrayList<>();
        dfs(0,0,list,target,temp,ans);
        return ans;
    }

    private void dfs(int k, int sum, List<Map.Entry<Integer, Integer>> list, int target, List<Integer> temp, List<List<Integer>> ans) {
        if (sum>target){
            return;
        }
        if (target==sum){
            ans.add(new ArrayList<>(temp));
            return;
        }
        if (k==list.size()){
            return;
        }
        dfs(k+1,sum,list,target,temp,ans);
        for (int i=0;i<list.get(k).getValue();i++){
            temp.add(list.get(k).getKey());
            dfs(k+1,sum+list.get(k).getKey()*(i+1),list,target,temp,ans);
        }
        for (int i=0;i<list.get(k).getValue();i++){
            temp.remove(temp.size()-1);
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution40().combinationSum2(new int[]{10,1,2,7,6,1,5},8));
    }
}
